﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.FindTargetSumWays
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 1,1,1,1,1 };
            int target = 3;
            Console.WriteLine(FindTargetSumWays(nums, target));
            Console.ReadKey();
        }


        /// <summary>
        /// 思路转换为二叉树    
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static int FindTargetSumWays(int[] nums, int target)
        {
            int index = -1;
            int sum = 0;
            int count = 0;
            BinaryTree(nums, target, 0, index,  sum, ref count);
            return count;
        }

        public static void BinaryTree(int[] nums, int target, int value, int index,  int sum, ref int count)
        {
            sum += value;
            index++;
            if (index == nums.Length && sum == target)
            {
                count++;
            }
            if (index>= nums.Length )
            {
                return;
            }

            BinaryTree(nums, target, nums[index], index,  sum, ref count);
            BinaryTree(nums, target, 0 - nums[index], index,  sum, ref count);
        }

    }
}
